#include <stdio.h>
#include <stdlib.h>

/*
 * 弗洛伊德：顶点i到顶点j的最短路径
 */

#define vertex_max 4
#define edge 8
#define max 32767

struct graph
{
  int arcs[vertex_max+1][vertex_max+1];
  int a[vertex_max+1][vertex_max+1];
  int path[vertex_max+1][vertex_max+1];
};

void floyd(struct graph * graph, const int vertex)
{
  int i, j, k;
  int next;

  for (i = 1; i <= vertex; i++)
    for (j = 1; j <= vertex; j++) {
      graph->a[i][j] = graph->arcs[i][j];
      if ((i != j) && (graph->a[i][j] < max))
	graph->path[i][j] = i;
      else
	graph->path[i][j] = 0;
    }

  for (k = 1; k <= vertex; k++) {
    for (i = 1; i<= vertex; i++)
      for (j = 1; j <= vertex; j++)
	if (graph->a[i][k] + graph->a[k][j] < graph->a[i][j]) {
	  graph->a[i][j] = graph->a[i][k] + graph->a[k][j];
	  graph->path[i][j] = graph->path[k][j];
	}
  }

  for (i = 1; i <= vertex; i++)
    for (j = 1; j <= vertex; j++) {
      if (i != j) {
	printf(" %d ", graph->a[i][j]);
	printf(":");

	next = graph->path[i][j];
	printf(" %d ", j);

	while (next != i) {
	  printf("<--- %d ", next);
	  next = graph->path[i][next];
	}
	
	printf("<--- %d\n ", i);
      }
    }
}

void main()
{
  struct graph graph;
  int i, j, w, k;

  for (i = 1; i <= vertex_max; i++)
    for (j = 1; j <= vertex_max; j++)
      if (i == j)
	graph.arcs[i][j] = 0;
      else
	graph.arcs[i][j] = max;

  for (k = 1; k <= edge; k++) {
    printf("input edge and edge of quan vuale:\n");
    scanf("%d %d %d", &i, &j, &w);
    graph.arcs[i][j] = w;
  }

  floyd(&graph, vertex_max);
}
